package day012;

import java.util.Scanner;

public class Test5_5 {

    static final int M = 105;
    static int n;                                                //表示n个皇后
    static int[] x = new int[M];                                   //表示第i个皇后放置在第i行第x[i]列
    static int countn;                                           //表示n皇后问题可行解个数

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入皇后的个数n：");
        n = scanner.nextInt();

        backTrack(1);                                            //进行搜索
        System.out.println("答案的个数是：" + countn);
    }

    /*按约束条件搜索求解*/
    public static void backTrack(int t) {
        if (t > n) {                                                //找到一个可行解
            countn++;
            for (int i = 1; i <= n; i++)
                System.out.print(x[i] + " ");                      //打印可行解
            System.out.println();
        } else {
            for (int i = 1; i <= n; i++) {                              //分别判断n个分支
                x[t] = i;
                if (place(t))
                    backTrack(t + 1);                              //若不冲突进行下一行的搜索
            }
        }
    }

    /*判断第t个皇后能否放置在第i个位置*/
    public static boolean place(int t) {
        boolean ok = true;
        for (int j = 1; j < t; j++) {                                   //判断该位置是否与前t-1个已经放置的皇后冲突
            if (x[t] == x[j] || t - j == Math.abs(x[t] - x[j])) {         //判断列。对角线是否冲突
                ok = false;
                break;
            }
        }
        return ok;
    }

}